package java_0305_sort;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 七大排序
 */
public class SevenSort {
    /**
     * 7.5三路快排
     */
    public static void quickSort3(int[] arr){
        quickSortInternal3(arr,0,arr.length-1);
    }
    private static void quickSortInternal3(int[] arr, int l, int r) {
        if(r-l<=15){
           insertionSort(arr,l,r);
            return;
        }
        int randomIndex=random.nextInt(l,r);
        swap(arr, l, randomIndex);
        int v=arr[l];//分区元素
        //变量的取值要满足区间定义，最开始的时候，所有区间取值得是空的
        //arr[l+1...lt]<v
        //lt指向最后一个<v的元素
        //lt是向后++的
        int lt=l;
        //arr[lt+1,i)==v
        int i=lt+1;
        //arr[gt,r]>v
        //gt是第一个>v的元素（gt是左移--的）
        int gt=r+1;
        //i从前向后扫描直到与gt重合时，所有元素就处理完毕了
        while(i<gt){
            if(arr[i]<v){
                swap(arr,i,lt+1);
                i++;
                lt++;
            }else if(arr[i]>v){
                swap(arr,i,gt-1);
                gt--;
                //此处i不++后移，因为换过来的gt-1对应元素没有处理，不知大小
            }else{
                i++;
            }
        }
        //循环结束，lt落在最后一个<v的索引处,交换lt与l索引位置的值，让v到lt索引处
        swap(arr,l,lt);
        //此时arr[l...lt-1]<v,在这个区间继续快排
        quickSortInternal3(arr,l,lt-1);
        //arr[gt...r]>v,在这个区间继续快排
        quickSortInternal3(arr,gt,r);
    }

    /**
     * 7.4挖坑法快排
     */
    public static void quickSortOfDigPit(int[] arr){
        quickSortOfDigPitInternal(arr,0,arr.length-1);
    }
    //    在arr[l...r]上进行快速排序
    private static void quickSortOfDigPitInternal(int[] arr, int l, int r) {
        if(r-l<=15){
            insertionSort(arr,l,r);//插入排序
            return;
        }
        //分区点
        int p=partitionDigPit(arr,l,r);
        //分区点左侧继续挖坑排序
        quickSortOfDigPitInternal(arr,l,p-1);
        //分区点右侧继续挖坑排序
        quickSortOfDigPitInternal(arr,p+1,r);
    }

    /**
     * 在arr[l...r]上挖坑法进行排序的分区处理
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partitionDigPit(int[] arr, int l, int r) {
        int randomIndex=random.nextInt(l,r);
        swap(arr,randomIndex,l);
        int i=l;
        int j=r;
        int v=arr[l];//也相当于左侧元素（分区点元素）被暂存了
        while(true){
            //必须先进行右侧向前扫描
            //j对应元素<v，循环暂停
            while(j>i&&arr[j]>=v){
                j--;
            }
            //直接把j处对应值给i
            arr[i]=arr[j];
            //i向后遍历，直到对应元素>v
            while(i<j&&arr[i]<=v){
                i++;
            }
            //i处对应元素直接覆盖j处对应元素
            arr[j]=arr[i];
            if(i>=j){
                //i>=j时，挖坑结束
                break;
            }
        }
        //此时挖坑结束，开始填坑，即把v值给arr[i]即可
        arr[i]=v;
        return i;
    }

    /**
     * 7.3二路快排
     */
    public static void quickSort2(int[] arr){
        quickSortInterna2(arr,0,arr.length-1);
    }

    private static void quickSortInterna2(int[] arr, int l, int r) {
        if(r-l<=15){
            insertionSort(arr, l, r);
            return;
        }
        int p=partition2(arr,l,r);
        quickSortInterna2(arr,l,p-1);
        quickSortInterna2(arr,p+1,r);
    }

    /**
     * 在arr[l...r]上进行双路快排的分区处理
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partition2(int[] arr, int l, int r) {
        int randomIndex=random.nextInt(l,r);
        swap(arr,randomIndex,l);
        int v=arr[l];
        //arr[l+1..i)<=v
        int i=l+1;
        //arr(j...r]>=v
        int j=r;
        while(true){
            //i从前向后扫描，碰到第一个>=v的元素停止
            while(i<=j&&arr[i]<v){
                i++;
            }
            //j从后向前扫描，碰到第一个<=v的元素停止
            while(j>=i&&arr[j]>v){
                j--;
            }
            if(i>=j){
                //循环遍历交换完毕
                break;
            }
            swap(arr,i,j);
            i++;
            j--;
        }
        //整个集合扫描完毕，j落在最后一个<=v的元素上
        swap(arr,l,j);
        return j;
    }
    /**
     * 7.2快排非递归分治
     */
    /**
     * 借助栈/队列来实现非递归分治的快排
     */
    public static void quickSortNonRecursion(int[] arr){
        Deque<Integer> stack=new ArrayDeque<>();
        //栈中保存当前集合的开始位置和终止位置
        int l=0;
        int r=arr.length-1;
        //先入后出
        stack.push(r);
        stack.push(l);
        while(!stack.isEmpty()){
            //栈不为空，说明子区间还未处理完毕
            int left=stack.pop();//left是区间左端点
            int right=stack.pop();
            if(left>=right){
                //区间只有一个元素，不需要再分区了
                continue;
            }
            int p=partition(arr,left,right);
            //依次将右区间的开始和结束位置压入栈中//先右后左压，取出来是先左后右
            stack.push(right);
            stack.push(p+1);
            //再将左侧区间开始和结束位置入栈
            stack.push(p-1);
            stack.push(left);
        }
    }

    /**
     * 7.1快排
     */
    private static final ThreadLocalRandom random=ThreadLocalRandom.current();
    public static void quickSort(int[] arr){
        quickSortInternal(arr,0,arr.length-1);
    }

    /**
     * 在arr[l...r]上进行快速排序
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal(int[] arr, int l, int r) {
        if(r-l<=15){
            insertionSort(arr,l,r);
            return;
        }
//        if(l>=r){
//            return;//只有一个元素时有序，不用再进行
//        }
        //先获取分区点
        //所谓分区点，就是经过分区函数后，某个元素落在了最终的位置
        //分区点左侧全是小于该元素的区间，分区点右侧都是>+该元素的区间
        int p=partition(arr,l,r);
        //递归重复在分区点的左区间和右区间上重复上述流程
        quickSortInternal(arr,l,p-1);
        quickSortInternal(arr,p+1,r);
    }

    /**
     * 在arr[l...r]上的分区函数，返回分区点的索引
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partition(int[] arr, int l, int r) {
        //随机在当前的数组中选一个数
        int randomIndex=random.nextInt(l,r);
        swap(arr,randomIndex,l);
        //基准值
        int v=arr[l];//此时arr[l]不一定是数组第一个元素，而是[l...r]间任意索引对应值
        //arr[l+1...j]<v
        //arr[j+1...i)>=v
        //i表示当前正在扫描的元素
        //最开始时上面两个区间没有元素，是空区间，赋值时注意
        int j=l;
        for (int i = l+1; i <= r; i++) {
            if(arr[i]<v){
                swap(arr,j+1,i);
                j++;
                //i++在循环条件里写了
            }//else arr[i]>v不需要交换只用i++
        }
        //走完循环交换基准值v和最后一个小于v的元素（j索引处）交换
        swap(arr,l,j);
        return j;//基准值对应索引
    }

    /**
     * 6.2归并排序的迭代写法
     */
    public static void mergeSortNonRecursion(int[] arr){
        //最外层循环表示每次合并的子数组的元素个数
        for (int sz=1;sz<= arr.length;sz+=sz){//先从1个元素开始合并
            //内层循环的变量i表示每次合并的开始索引
            //i+size就是右区间的开始索引，i+size<arr.length说明还存在右区间
            for (int i=0;i+sz< arr.length;i+=sz+sz){//sz+sz是下一次合并的开始索引
                merge(arr,i,i+sz-1,Math.min(i+sz+sz-1, arr.length-1));//传入arr,left,mid,right
                //Math.min取右区间与arr.length的最小值，因为有可能i+sz+sz-1会走到null
            }
        }
    }
    /**
     * 6.1归并排序-递归
     */
    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr,0,arr.length - 1);
    }

    /**
     * 在arr[l...r]进行归并排序,整个arr经过函数后就是一个已经有序的数组
     * @param arr
     * @param l
     * @param r
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {
        //归
//        if(l>=r){
//            //当前数组只剩一个元素，归过程结束
//            return;
//        }
        if(r-l<=15){
            insertionSort(arr,l,r);
            return;
        }
        int mid=l+((r-l)>>1);
        //将原数组拆分成左右两个小区间，分别递归的进行归并排序
        mergeSortInternal(arr,l,mid);//走完这个函数之后arr[l...mid]已经有序
        mergeSortInternal(arr,mid+1,r);//走完这个函数后[mid+1...r]已经有序
        //只有两个子区间还有先后顺序不同时，才merge
        if(arr[mid]>arr[mid+1]){//左区间最大值>右区间最小值才merge
            merge(arr,l,mid,r);
        }
    }

    /**
     * 在arr[l...r]使用直接插入排序
     * 归并排序中，一般r-l<=15时，使用插入排序，不必归并到1
     * @param arr
     * @param l
     * @param r
     */
    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l+1; i <=r ; i++) {
            for (int j = i; j >l&&arr[j]<arr[j-1]; j--) {
                swap(arr,j,j-1);
            }
            
        }
    }

    /**
     * 合并两个子数组arr[l...mid],arr[mid+1...r]
     * 为一个大的有序数组arr[l...r]
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        //先创建一个新的临时组数aux
        int[] aux=new int[r-l+1];//数组长度与索引有一个1的差值
        //将arr元素值拷贝到aux上
        for (int i = 0; i < aux.length; i++) {
            //arr的left不一定从索引0开始，它从left（l）开始，与aux的i刚好差了l个单位
            //如合并15、47举例，值1的索引是4，他要放在aux[0]位置，即aux[0]=arr[0+4],l恰好是4
            aux[i]=arr[i+l];
        }
        //此时临时数组aux的值已经拷贝好了
        //k表示当前正在合并的原数组的索引下标；i是左侧小数组的开始索引，j是右侧小数组的开始索引
        int i=l;
        int j=mid+1;
        for (int k = l; k <=r ; k++) {
            if(i>mid){
                //左侧区间已经处理完毕，只需要将右侧区间的值拷贝到原数组即可
                arr[k]=aux[j-l];//j表示原数组索引，对应aux上的索引是有l个单位的偏移量
                j++;
            }else if(j>r){
                //右侧区间已经被处理完毕，只需要将左侧区间的值拷贝到原数组即可
                arr[k]=aux[i-l];
            }else if(aux[i-l]<=aux[j-l]){
                //此时左区间元素较小//等于号放在左区间，保证排序的稳定性
                arr[k]=aux[i-l];
                i++;
            }else{
                //右侧区间元素值较小
                arr[k]=aux[j-l];
                j++;
            }
        }
    }

    /**
     * 5希尔排序
     */
    public static void shellSort(int[] arr){
        int gap= arr.length>>1;
        while(gap>1){
            insertionSortByGap(arr,gap);
            gap=gap>>1;
        }
        insertionSort(arr);
    }

    /**
     * 按gap分组进行插入排序
     * @param arr
     * @param gap
     */
    private static void insertionSortByGap(int[] arr,int gap) {
        for (int i = gap; i < arr.length; i++) {
            for (int j = i; j-gap >=0&&arr[j]<arr[j-gap] ; j-=gap) {
                swap(arr,j,j-gap);
            }
        }
    }

    /**
     * 4.2折半插入排序
     */
    public static void insertionSortBS(int[] arr){
        //有序区间[0,i)
        //无序区间[i,n)
        for (int i = 1; i < arr.length; i++) {
            //当前遍历的元素
            int val=arr[i];
            int left=0;
            int right=i;//i取不到
            while(left<right){
                int mid=left+((right-left)>>1);
                if(val<arr[mid]){
                    right=mid;//不用mid-1，因为right本身是取不到的
                }else{
                    //val>=mid
                    left=mid+1;
                }
            }
            //搬移left...i的元素
            for (int j = i; j >left ; j--) {
                arr[j]=arr[j-1];//后一个元素等于前一个元素
            }
            //left就是val插入的位置
            arr[left]=val;
        }
    }
    /**
     * 4.1直接插入排序
     * 已排序区间[0,i)
     * 待排序区间[i,n]
     * 每次从无序区间中拿第一个值插入到排序区间的合适位置，直到数组有序
     */
    public static void insertionSort(int[] arr){
        //从第二个元素开始，默认第一个元素是已排好序的元素
        for (int i = 1; i < arr.length; i++) {
            //待排序区间的第一个元素：arr[i]
            //从待排序区间的第一个元素向前看，找到合适插入位置
            /**
             * 1.
             */
//            for (int j = i; j >0 ; j--) {
//                if(arr[j]>=arr[j-1]){//arr[j]：待排序区间第一个元素；arr[j-1]:已排序区间最后一个元素
//                    //此时说明j索引对应元素比排序区间所有值都大,arr[j]已经有序了，直接进行下次循环
//                    //注意：相等也放在判断条件中，即相等也不进行交换，保证稳定性
//                    break;
//                }else{
//                    swap(arr,j,j-1);
//                }
//            }
            /**
             * 2.=》1等价于2
             */
//            for (int j = i; j >0&&arr[j]<arr[j-1]; j--) {
//                swap(arr,j,j-1);
//            }
            /**
             * 3.无需进行交换操作
             */
//            int j = i;
//            int val=arr[j];
//            for (; j >0 ; j--) {
//                if(val>=arr[j-1]){
//                    arr[j]=val;
//                    break;
//                }else{
//                    arr[j]=arr[j-1];
//                }
//            }
//            arr[j]=val;
            int j=i,val=arr[j];
            for(;j>0&&val<arr[j-1];j--){
                arr[j]=arr[j-1];
            }
            arr[j]=val;
        }
    }
    /**
     * 3.2双向选择排序
     */
    public static void selectionSortOP(int[] arr){
        int low=0;
        int high= arr.length-1;
        //low==high,无序区间只剩一个元素，整个区间已经有序
        while (low<=high){
            int min=low;
            int max=low;
            for (int i = low+1; i <= high; i++) {
                if(arr[i]<arr[min]){
                    min=i;
                }
                if(arr[i]>arr[max]){
                    max=i;
                }
            }
            //此时min索引一定是当前无序区间的最小值索引，把这个最小值与low索引处的值交换
            swap(arr,min,low);
            if(max==low){
                //若最大值恰好在low位置，则最小值交换后，最大值已经被换到min这个位置了，max应该=min
                max=min;
            }
            swap(arr,max,high);
            low+=1;
            high-=1;
        }
    }
    /**
     * 3.1选择排序
     */
    public static void selectionSort(int[] arr){
        //最开始无序区间[0...n]，有序区间[]
        //arr.length-1:当无需区间只剩一个元素时，整个集合已经有序，所以可以少走一次（-1）
        for (int i = 0; i < arr.length-1; i++) {
            //min变量存储了当前的最小值索引，先默认第一个元素是最小值
            int min=i;
            //j从i+1开始，因为第一个i元素已经被选择过了，从第二个元素开始走（自己和自己不比较）
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[min]){
                    min=j;
                }
            }
            //此时min索引一定对应了当前无序区间找到的最小值索引，将它换到无序区间最前面i索引处
            swap(arr,min,i);
        }
    }





    //n*n时间复杂度的排序【冒泡排序法】
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            boolean isSwaped=false;
            for (int j = 0; j < arr.length - 1-i; j++) {
                if (arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    isSwaped=true;
                }
            }
            if(!isSwaped){
                break;
            }
        }
    }
    //传入一个arr把它进行一个堆排序
    public static void heapSort(int[] arr){
        //1.先将arr进行heapify操作调整为最大堆
        //heapify:从最后一个非叶子节点开始进行siftDown操作
        for (int i = (arr.length-1-1)/2; i >= 0 ; i--) {
            siftDown(arr,i,arr.length);//传入arr,下沉的位置的索引，数组长度
        }
        //此时arr就被调整为一个最大堆了
        for (int i = arr.length-1; i >0 ; i--) {
            //arr[0]:堆顶元素，就是当前堆的最大值，把它换到最后
            swap(arr,0,i);
            //换完继续执行下沉操作:从0->i位置
            siftDown(arr,0,i);
        }//换完就是一个升序有序数组了
    }

    /**
     * 元素下沉操作
     * @param arr
     * @param i 当前要下沉的索引
     * @param length 数组长度
     */
    private static void siftDown(int[] arr, int i, int length) {
        //当有左右孩子才能进行下沉
        while (2*i+1<length){
            int j=(i<<1)+1;
            if(j+1<length&&arr[j+1]>arr[j]){
                j=j+1;
            }
            //此时j是左右子树最大值的索引
            if(arr[i]>arr[j]){
                //元素下沉结束
                break;
            }else{
                //交换i和j位置的值
                swap(arr,i,j);
                //i等于j继续向后下沉判断
                i=j;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public static void main(String[] args) {//测试
        int[] arr={7,5,4,3,2,1,9,10,8,6};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
//    public static void main(String[] args) {//测试
//        int[] arr={9,2,5,7,5,4,3,6};
//        selectionSort(arr);
//        System.out.println(Arrays.toString(arr));
////        int n=100000;
////        int[] arr=new int[n];
////        //生成随机数
////        ThreadLocalRandom random=ThreadLocalRandom.current();
////        for (int i = 0; i < n; i++) {
////            arr[i]=random.nextInt(0,Integer.MAX_VALUE);
////        }
////        int[] arr1=Arrays.copyOf(arr,n);//拷贝一份arr
////        //对arr做冒泡排序，对arr1做堆排序
////        Long start=System.nanoTime();//当前的系统时间
////        //冒泡排序
////        bubbleSort(arr);
////        Long end=System.nanoTime();//当前时间(nanoTime是纳秒)
////        if(isSorted(arr)){
////            System.out.println("冒泡排序共耗时："+(end-start)/1000000+"ms");
////        }
////        /**
////         * 堆排序
////         */
////        start=System.nanoTime();//当前的系统时间
////        heapSort(arr1);
////        end=System.nanoTime();//当前时间(nanoTime是纳秒)
////        if(isSorted(arr1)){
////            System.out.println("堆排序共耗时："+(end-start)/1000000+"ms");
////        }
//    }
//    public static boolean isSorted(int[] arr){
//        for (int i = 0; i < arr.length-1; i++) {
//            if(arr[i]>arr[i+1]){
//                System.out.println("sort error");
//                return false;
//            }
//        }
//        return true;
//    }
}
